package org.example.myleet.p442;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Solution {

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>(nums.length);
        boolean[] exist = new boolean[nums.length];
        for (int num : nums) {
            if (exist[num - 1]) {
                result.add(num);
            } else {
                exist[num - 1] = true;
            }
        }
        return result;
    }

//    public List<Integer> findDuplicates(int[] nums) {
//        HashSet<Integer> result = new HashSet<>(nums.length);
//        for (int i = 0; i < nums.length; ++i) {
//            int idx = nums[i] - 1;
//            //通过交换不断完成排序
//            while (i != idx && nums[i] != nums[idx]) {
//                int t = nums[i];
//                nums[i] = nums[idx];
//                nums[idx] = t;
//                idx = nums[i] - 1;
//            }
//            if (i != idx && nums[i] == nums[idx]) {
//                //完成交换排序时发现相同的数出现在不同位置，记录下来
//                result.add(nums[i]);
//            }
//        }
//        return new ArrayList<>(result);
//    }

//    public List<Integer> findDuplicates(int[] nums) {
//        List<Integer> result = new ArrayList<>(nums.length);
//        HashSet<Integer> appearance = new HashSet<>(nums.length);
//        for (int num : nums) {
//            if (appearance.contains(num)) {
//                result.add(num);
//            } else {
//                appearance.add(num);
//            }
//        }
//        return result;
//    }
}
